package consistenthash

import (
	"log"
	"os"
	"sync"
)

type K interface{}
type V interface{}

type TreeMap struct {
	root     *Entry //根
	size     int
	modCount int
	lock     sync.Mutex
	logger   *log.Logger
}
func NewTreeMap()*TreeMap{
	return &TreeMap{
		root: nil,
		size: 0,
		modCount: 0,
		logger: log.New(os.Stderr, "[treeMap] ", log.LstdFlags),
	}
}

func Key(e *Entry) K {
	return e.key
}
func (t *TreeMap) Size() int {
	return t.size
}

func (t *TreeMap) FirstEntry() *Entry {
	p := t.root
	if p != nil {
		for p.left != nil {
			p = p.left
		}
	}
	return p
}

func (t *TreeMap) LastEntry() *Entry {
	p := t.root
	if p != nil {
		for p.right != nil {
			p = p.right
		}
	}
	return p
}
// GetCeilingEntry 获取比参数k大的第一个节点
func (t *TreeMap) GetCeilingEntry(k K) *Entry {
	p := t.root
	for p != nil {
		cmp := k.(int64) - p.key.(int64)
		if cmp > 0 {
			if p.right != nil {
				p = p.right
			} else {
				return p
			}
		} else if cmp < 0 {
			if p.right != nil {
				p = p.right
			} else {
				parent := p.parent
				ch := p
				for parent != nil && ch == parent.right {
					ch = parent
					parent = parent.parent
				}
				return parent
			}
		} else {
			return p
		}
	}
	return nil
}

func (t *TreeMap) Get(key K) V {
	var p *Entry = t.getEntry(key)
	if p == nil {
		return nil
	}
	return p.value
}

func (t *TreeMap) Put(k K, v V) V {
	_,ok:=k.(int64)
	if !ok{
		t.logger.Printf("only support key type int64\n")
		return nil
	}
	r := t.root
	if r == nil {
		t.root = NewEntry(k, v, nil)
		t.size = 1
		t.modCount++
		return nil
	}
	var cmp int64
	var parent *Entry
	for {
		parent = r
		cmp = k.(int64) - r.key.(int64)
		if cmp < 0 {
			r = r.left
		} else if cmp > 0 {
			r = r.right
		} else {
			return r.SetValue(v)
		}
		if r == nil {
			break
		}
	}
	e := NewEntry(k, v, parent)
	if cmp < 0 {
		parent.left = e
	} else {
		parent.right = e
	}
	t.size++
	t.modCount++
	return nil
}
func (t *TreeMap) getEntry(key K) *Entry {
	p := t.root
	if p == nil {
		return nil
	}
	_, ok1 := t.root.key.(int64)
	k2, ok2 := key.(int64)
	if !ok1 || !ok2 {
		t.logger.Println("only suppose long currently")
		return nil
	}
	for p != nil {
		k1, _ := p.key.(int64)
		cmp := k2 - k1
		if cmp < 0 {
			p = p.left
		} else if cmp > 0 {
			p = p.right
		} else {
			return p
		}
	}
	return nil
}

type Entry struct {
	key    K
	value  V
	left   *Entry
	right  *Entry
	parent *Entry
	color  bool
}

func NewEntry(k K, v V, parent *Entry) *Entry {
	e := &Entry{}
	e.key = k
	e.value = v
	e.parent = parent
	return e
}
func (e *Entry) GetKey() K {
	return e.key
}
func (e *Entry) GetValue() V {
	return e.value
}
func (e *Entry) SetValue(v V) V {
	oldValue := e.value
	e.value = v
	return oldValue
}
func (e *Entry) SetKey(k V) {
	e.key = k
}
func (e *Entry) Equals(obj *Entry) bool {
	if e == obj {
		return true
	}
	return e.key == obj.GetKey() && e.value == obj.GetValue()
}
